package LeetCode.leetcode198;

import java.util.Arrays;

class Solution {
    /**
     * solution 1
     * @param nums
     * @return
     */
//    public int rob(int[] nums) {
//        int[] memo = new int[nums.length];
//        Arrays.fill(memo, -1);
//        return dfs(nums, nums.length - 1, memo);
//    }
//    public int dfs(int[] nums,int endIndex,int[] memo) {
//        if (endIndex == 0) return nums[0];
//        if (endIndex == 1) return Math.max(nums[0], nums[1]);
//        if (memo[endIndex] != -1) return memo[endIndex];
//        return memo[endIndex] = Math.max(dfs(nums, endIndex - 1, memo), dfs(nums, endIndex - 2, memo) + nums[endIndex]);
//    }

    /**
     * solution 2
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}